\chapter{Introdução}
Neste primeiro capítulo definimos um problema de programação linear (PPL) e seus derivados e posteriormente apresentamos uma lista dos principais PPLs.

\section{Definição de PPL}
Antes de definirmos um PPL é interessante definirmos um poliedro.
\begin{defi}[Poliedro]
 Seja $A_{o \times n}$, $B_{p \times n}$ e $C_{q \times n}$ três matrizes e $\mathbf{a}_o$, $\mathbf{b}_p$, $\mathbf{c}_q$ e $\mathbf{x}_n$ quatro vetores. Dizemos que $P$ definido como
 \[
  P = \{\mathbf{x}: A\mathbf{x} \leq \mathbf{a}, B\mathbf{x} \geq \mathbf{b}, C\mathbf{x} = \mathbf{c} \}
 \]
 é um poliedro.
\end{defi}

Todo PPL é definido em relação a um poliedro, $P$, e uma função linear, $f(\mathbf{x})$, denominada função objetivo. Inicialmente podemos dividir os PPL em dois grupos, os PPLs de minimização e os de maximização.\footnote{Como será visto no próximo capítulo podemos escrever um PPL de minimização como de maximização e vice-versa.}
\begin{defi}[PPL de minimização]
 Um PPL de minimização, denotado por $\{ \mbox{min } f(\mathbf{x}): \mathbf{x} \in P \}$, corresponde a encontrar $\mathbf{x}$ tal que $\mathbf{x} \in P$ e $f(\mathbf{x})$ seja mínimo.
\end{defi}
\begin{defi}[PPL de maximização]
 Um PPL de maximização, denotado por $\{ \mbox{max } f(\mathbf{x}): \mathbf{x} \in P \}$, corresponde a encontrar $\mathbf{x}$ tal que $\mathbf{x} \in P$ e $f(\mathbf{x})$ seja máximo.
\end{defi}

Dizemos que $\mathbf{x}^*$ é solução do PPL de minimização dado por $\{ \mbox{min } f(\mathbf{x}): \mathbf{x} \in P \}$ se não existe $\mathbf{x} \in P$, com $\mathbf{x} \neq \mathbf{x}^*$, tal que $f(\mathbf{x}) < f(\mathbf{x}^*)$.

Existem duas classes de problemas que podem ser vistos como casos específicos de um PPL. A primeira delas corresponde aos problemas de programação inteira\footnote{É importante destacar que vários problemas de programação combinatória podem ser escritos como um problema de programação inteira.} (PPI) cuja solução $\mathbf{x}^*$ deve ser inteira, isso é, todas as entradas de $\mathbf{x}^*$ são números inteiros. A segunda delas corresponde aos problemas de fluxos em redes (PFR), isso é, problemas descritos a partir de grafos.

\section{PPLs Clássicos}
A seguir descrevermos vários PPLs, PPIs e PFRs que já foram bastante estudados. Para cada problema também apresentamos uma modelagem, alguns exemplos reais e sugestões de leituras adicionais.

Vale destacar que os problemas encontra-se ordenados em ordem alfabética e que ao longo do livro iremos preferir a nomenclatura inglesa para os problemas pois alguns problemas admitem mais de uma tradução.

\subsection{\textit{Assignment Problem}}\index{Assignment Problem@\textit{Assignment Problem}}
O \textit{Assignment Problem}, Problema de Designação\index{Problema de Designação|see{\textit{Assignment Problem}}} ou Problema de Atribuição\index{Problema de Atribuição|see{\textit{Assignment Problem}}} é um caso especial do \textit{Transportation Problem} que consiste em encontrar o emparelhamento de menor custo em um grafo bipartido.

\begin{descr}[\textit{Assignment Problem}]\index{Assignment Problem@\textit{Assignment Problem}!Enunciado}\nocite{Ahuja:1993:NFT:137406}
 Dados dois conjuntos $N_1$ e $N_2$ de mesma cardinalidade, um conjunto $A$ de pares $(i,j)$, com $i \in N_1$ e $j \in N_2$, e  custos $c_{(i,j)}$ para todo $(i,j) \in A$. Desejamos encontrar um subconjunto $X$ de $A$ de custo mínimo, $\sum_{(i,j) \in X} c_{(i,j)}$, tal que em $X$ não existe $(i,j)$ e $(i,j')$, com $j \neq j'$, nem $(i,j)$ e $(i',j)$, com $i \neq i'$.
\end{descr}

\begin{model}[\textit{Assignment Problem}]\index{Assignment Problem@\textit{Assignment Problem}!Modelo}
 Seja $N_1 = N_2 = \{ 1, 2, \ldots, n \}$. Seja $x_{(i,j)} = 1$ se o par $(i,j) \in X$ e $x_{(i,j)} = 0$ caso contrário.
 \[
  \begin{array}{lll}
   \mbox{min} & \displaystyle \sum_{i = 1}^n \sum_{j = 1}^n c_{(i,j)} x_{(i,j)} & \\
   \mbox{sa } & \displaystyle \sum_{i = 1}^n x_{(i,j)} = 1, & \forall j \in \{ 1, 2, \ldots, n\} \\
   & \displaystyle \sum_{j = 1}^n x_{(i,j)} = 1, & \forall i \in \{ 1, 2, \ldots, n\}
  \end{array}
 \]
\end{model}

Os principais exemplos são: designação de pessoas para projetos, trabalhos para máquinas, \ldots

\subsection{\textit{Circulation Problem}}\index{Circulation Problem@\textit{Circulation Problem}}
O \textit{Circulation Problem} ou Problema de Circulação\index{Problema de Circulação|see{\textit{Circulation Problem}}} trata de encontrar o fluxo factível de custo mínimo para uma dada rede.

\begin{descr}[\textit{Circulation Problem}]\index{Circulation Problem@\textit{Circulation Problem}!Descrição}
 Dado um conjunto $N$, um conjunto $A$ de pares $(i,j)$, com $i,j \in N$, limites inferiores, $l_{(i,j)}$, e superiores, $u_{(i,j)}$, ($l_{(i,j)} \leq u_{(i,j)}$, para todo $(i,j) \in A$ e custos $c_{(i,j)}$ para todo $(i,j) \in A$. Desejamos encontrar valores $x_{(i,j)}$ para todo $(i,j) \in A$ tal que o custo do fluxo na rede, $\sum_{(i,j) \in X} c_{(i,j)} x_{(i,j)}$, seja mínimo, $l_{(i,j)} \leq x_{(i,j)} \leq u_{(i,j)}$ e ocorra a conservação de fluxo.
\end{descr}

\begin{model}[\textit{Circulation Problem}]\index{Circulation Problem@\textit{Circulation Problem}!Modelo}
 Seja $N = \{ 1, 2, \ldots, n \}$. Seja $x_{(i,j)}$ o fluxo correspondente ao par $(i,j)$, $i,j \in N$.
 \[
  \begin{array}{lll}
   \mbox{min} & \displaystyle \sum_{i = 1}^n \sum_{j = 1}^n c_{(i,j)} x_{(i,j)} & \\
   \mbox{sa} & \displaystyle \sum_{i = 1}^n x_{(i,j)} - x_{(j,i)} = 0, & \forall j \in N \\
   & l_{(i,j)} \leq x_{(i,j)} \leq u_{(i,j)} & \forall i,j \in N
  \end{array}
 \]
\end{model}

Os principais exemplos são: agendamento de aviões de uma companhia aérea comercial.

% \subsection{\textit{Convex Cost Flow Problem}}\index{Convex Cost Flow Problem@\textit{Convex Cost Flow Problem}}

\subsection{\textit{Cutting Stock Problem}}\index{Cutting Stock Problem@\textit{Cutting Stock Problem}}\nocite{Bazaraa:1990:LPN:77656}
O \textit{Cutting Stock Problem}, \textit{Cutting Problem}\index{Cutting Problem@\textit{Cutting Problem}|see{\textit{Cutting Stock Problem}}} ou Problema de Corte\index{Problema de Corte|see{\textit{Cutting Stock Problem}}} trata de encontrar uma forma de dividir uma mercadoria em porções menores de maneira a atender certa demanda tal que o desperdício de mercadoria seja minimizado. Esse problema apresenta versões unidimensionais, bidimensionais e tridimensionais sendo que apenas iremos abordar a versão unidimensional.

\begin{descr}[\textit{Cutting Stock Problem}]\index{Cutting Stock Problem@\textit{Cutting Stock Problem}!Descrição}
 Suponhamos que existam $n$ barras de comprimento $l$, $p$ formas de cortar essas barras em porções menores e deseje-se $b_i$ barras de comprimento $l_i$, com $i \in \{ 1, 2, \ldots, m \}$. Deseja-se encontrar uma forma de cortar as barras iniciais de modo que ao final do processo seja obtido a configuração de barras desejadas e o desperdício seja minimizado.
\end{descr}

\begin{model}[\textit{Cutting Stock Problem}]\index{Cutting Stock Problem@\textit{Cutting Stock Problem}!Modelo}
 Seja $N = \{ 1, 2, \ldots, n \}$ as barras iniciais, $P = \{ 1, 2, \ldots, p \}$ as formas de corte.
 \[
  \begin{array}{lll}
   \mbox{min} & \displaystyle \sum_{j = 1}^n x_j & \\
   \mbox{sa} & \displaystyle \sum_{j = 1}^n a_{ij} x_j \geq b_j, & \forall i \in \{ 1, 2, \ldots, m \} \\
   & x_j \in \mathbb{Z}_\geq & \forall j \in \{ 1, 2, \ldots, n \}
  \end{array}
 \]
\end{model}

O principal exemplo é o corte de algum material.


\subsection{\textit{Feed Mix Problem}}\index{Feed Mix Problem@\textit{Feed Mix Problem}}\nocite{Bazaraa:1990:LPN:77656}
O \textit{Feed Mix Problem} ou Problema da Ração\index{Problema da Ração|see{\textit{Feed Mix Problem}}} corresponde a encontra a quantidade de certos ingredientes que compõe determinada mistura que satisfa\ determinados níveis nutricionais e tem custo mínimo.

\begin{descr}[Feed Mix Problem]\index{Feed Mix Problem@\textit{Feed Mix Problem}!Descrição}
Seja $N = \{ 1, 2, \ldots, n \}$ um conjunto de ingredientes e $M = \{ 1, 2, \ldots, m \}$ um conjunto de nutrientes. Seja $c_j$ e $x_j$, respectivamente, o custo unitário e a quantidade utilizada do ingrediente $j \in N$. Seja $l_i$ e $u_i$, respectivamente, os limites inferiores e superiores aceitáveis para o nutriente $j \in M$.  Seja $a_{ij}$ a quantidade do nutriente $i \in M$ existente em cada unidade no ingrediente $j \in N$. Desejamos encontrar valores de $x_j$ tal que o custo da mistura seja mínimo, $\sum_{j=1}^n c_j x_j$, e que apresente valor nutricional entre os limites aceitáveis.
\end{descr}

\begin{model}[Feed Mix Problem]\index{Feed Mix Problem@\textit{Feed Mix Problem}!Modelo}
\[
 \begin{array}{lll}
  \mbox{min} & \displaystyle \sum_{j = 1}^n c_j x_j & \\
  \mbox{sa} & \displaystyle l_i \leq \sum_{j = 1}^n a_{ij} x_j \leq u_i, & \forall j \in \{ 1, 2, \ldots, m \} \\
  & x_j \geq 0, & \forall j \in \{ 1, 2, \ldots, n \}
 \end{array}
\]
\end{model}

Os principais exemplos são: ração para animais, fertilizantes sintéticos, vitaminas em cápsulas.

\subsection{\textit{Generalized Flow Problem}}\index{Generalized Flow Problem@\textit{Generalized Flow Problem}}\nocite{Ahuja:1993:NFT:137406}
O \textit{Generalized Flow Problem} ou Problema de Fluxo Generalizado\index{Problema de Fluxo Generalizado|see{\textit{Generalized Flow Problem}}} trata de encontrar o fluxo factível de custo mínimo para uma dada rede na qual em cada arco existe um ganho associado.

\begin{descr}[\textit{Generalized Flow Problem}]\index{Generalized Flow Problem@\textit{Generalized Flow Problem}!Descrição}
 Dado um conjunto $N$, um conjunto $A$ de pares $(i,j)$, com $i,j \in N$, limite inferior, $l_{(i,j)}$, e superior, $u_{(i,j)}$, ($l_{(i,j)} \leq u_{(i,j)}$, para todo $(i,j) \in A$, ganho $\mu_{(i,j)} > 0$ para todo $(i,j) \in A$ e custo $c_{(i,j)}$ para todo $(i,j) \in A$. Desejamos encontrar valores $x_{(i,j)}$ para todo $(i,j) \in A$ tal que o custo do fluxo na rede, $\sum_{(i,j) \in X} c_{(i,j)} x_{(i,j)}$, seja mínimo, $l_{(i,j)} \leq x_{(i,j)} \leq u_{(i,j)}$ e ocorra a conservação de fluxo.
\end{descr}

\begin{model}[\textit{Generalized Flow Problem}]\index{Generalized Flow Problem@\textit{Generalized Flow Problem}!Modelo}
 Seja $N = \{ 1, 2, \ldots, n \}$. Seja $x_{(i,j)}$ o fluxo correspondente ao par $(i,j)$, $i,j \in N$.
 \[
  \begin{array}{lll}
   \mbox{min} & \displaystyle \sum_{i = 1}^n \sum_{j = 1}^n c_{(i,j)} x_{(i,j)} & \\
   \mbox{sa} & \displaystyle \sum_{i = 1}^n \mu_{(i,j)} x_{(i,j)} - \mu_{(j,i)} x_{(j,i)} = 0, & \forall j N \\
   & l_{(i,j)} \leq x_{(i,j)} \leq u_{(i,j)} & \forall i,j \in N
  \end{array}
 \]
\end{model}

Os principais exemplos são: transmissão de energia em linhas elétricas, fluxo de água em canais, transporte de material perecível, \ldots

\subsection{\textit{Job-shop Problem}}\index{Job-shop Problem@\textit{Job-shop Problem}}\nocite{Ahuja:1993:NFT:137406}
O \textit{Job-shop Problem}, \textit{Scheduling Problem}\index{Scheduling Problem@\textit{Scheduling Problem}|see{\textit{Job-shop Problem}}}, Problema do Escalonamento de Tarefas\index{Problema do Escalonamento de Tarefas|see{\textit{Job-shop Problem}}} ou Problema da Agenda\index{Problema da Agenda|see{Job-shop Problem}} é uma generaliza\c{c}\~ao do \textit{Travelling Salesman Problem}\index{Travelling Salesman Problem@\textit{Travelling Salesman Problem}!Generaliza\c{c}\~ao} e trata encontrar a escala para os elementos de um conjunto que precisam realizar as tarefas de um outro conjunto.

\begin{descr}[\textit{Job-shop Problem}]\index{Job-shop Problem@\textit{Job-shop Problem}!Descrição}
 
\end{descr}

\begin{model}\index{Job-shop Problem@\textit{Job-shop Problem}!Modelo}
 
\end{model}

O principal exemplo é a cadeia de produção de uma fábrica.


\subsection{\textit{Matching Problem}}\index{Matching Problem@\textit{Matching Problem}}
O \textit{Matching Problem} ou Problema de Emparelhamento\index{Problema de Emparelhamento|see{\textit{Matching Problem}}} trata de encontrar o emparelhamento de custo mínimo para um dado grafo.

\begin{descr}[\textit{Matching Problem}]\index{Matching Problem@\textit{Matching Problem}!Descrição}
 
\end{descr}

\begin{model}[\textit{Matching Problem}]\index{Matching Problem@\textit{Matching Problem}!Modelo}
 
\end{model}




\subsection{\textit{Maximum Flow Problem}}\index{Maximum Flow Problem@\textit{Maximum Flow Problem}}

\begin{descr}[\textit{Maximum Flow Problem}]\index{Maximum Flow Problem@\textit{Maximum Flow Problem}!Descrição}
 
\end{descr}

\begin{model}[\textit{Maximum Flow Problem}]\index{Maximum Flow Problem@\textit{Maximum Flow Problem}!Modelo}
 
\end{model}



\subsection{\textit{Minimum Cost Flow Problem}}\index{Minimum Cost Flow Problem@\textit{Minimum Cost Flow Problem}}

\begin{descr}[\textit{Minimum Cost Flow Problem}]\index{Minimum Cost Flow Problem@\textit{Minimum Cost Flow Problem}!Descrição}
 
\end{descr}

\begin{model}[\textit{Minimum Cost Flow Problem}]\index{Minimum Cost Flow Problem@\textit{Minimum Cost Flow Problem}!Modelo}
 
\end{model}



\subsection{\textit{Minimum Spanning Tree Problem}}\index{Minimum Spanning Tree Problem@\textit{Minimum Spanning Tree Problem}}

\begin{descr}[\textit{Minimum Spanning Tree Problem}]\index{Minimum Spanning Tree Problem@\textit{Minimum Spanning Tree Problem}!Descrição}
 
\end{descr}

\begin{model}[\textit{Minimum Spanning Tree Problem}]\index{Minimum Spanning Tree Problem@\textit{Minimum Spanning Tree Problem}!Modelo}
 
\end{model}



% \subsection{\textit{Multicommodity Flow Problem}}\index{Multicommodity Flow Problem@\textit{Multicommodity Flow Problem}}

\subsection{\textit{Shortest Path Problem}}\index{Shortest Path Problem@\textit{Shortest Path Problem}}

\begin{descr}[\textit{Shortest Path Problem}]\index{Shortest Path Problem@\textit{Shortest Path Problem}!Descrição}
 
\end{descr}

\begin{model}[\textit{Shortest Path Problem}]\index{Shortest Path Problem@\textit{Shortest Path Problem}!Modelo}
 
\end{model}



\subsection{\textit{Transportation Problem}}\index{Transportation Problem@\textit{Transportation Problem}}

\begin{descr}[\textit{Transportation Problem}]\index{Transportation Problem@\textit{Transportation Problem}!Descrição}
 
\end{descr}

\begin{model}[\textit{Transportation Problem}]\index{Transportation Problem@\textit{Transportation Problem}!Modelo}
 
\end{model}



\subsection{\textit{Travelling Salesman Problem}}\index{Travelling Salesman Problem@\textit{Travelling Salesman Problem}}

\begin{descr}[\textit{Travelling Salesman Problem}]\index{Travelling Salesman Problem@\textit{Travelling Salesman Problem}!Descrição}
 
\end{descr}

\begin{model}[\textit{Travelling Salesman Problem}]\index{Travelling Salesman Problem@\textit{Travelling Salesman Problem}!Modelo}
 
\end{model}


